Distributed processing system is used herein to describe a system in which a plurality of independent, interconnected, arithmetical-logical processor elements operate in parallel to perform a multiplicity of processing functions. The processors in the system are, typically, substantially identical to one another. The processors are preferably interconnected in a manner enabling communication between any pair of processors. In one type of parallel processing system known in the art as a single instruction multiple data (SIMD) system, a single sequence of instructions is provided to all processors. That is, all processors simultaneously perform operations in accordance with the same sequence of instructions. However, each processor may be performing the operations dictated by the instructions on different sets of data.
The individual processors of a SIMD parallel processing system typically have dedicated memory which may be loaded with data on which instructed operations can be performed. Also, each processor can read and write information at another processor. Thus, there is a flexibility in the operations performed by each processor insofar as derives from varying the data upon which each processor operates.
Various types of calculations are especially well suited for processing on a distributed processing system. Image processing problems represent one class of calculations that are well suited for and facilitated by processing on a distributed processing system. Frequently, calculations performed on a distributed processing system include manipulation of data strings. A data string as used herein is a sequence of data elements in which each string element is related to the next element in the string, for example by a pointer. It is frequently necessary in manipulating data strings to determine the length of each string. The length of a data string is the number of elements of which it is composed. Such length information is not immediately determinable since each string element only carries, by its pointer, the identity of an immediately succeeding element in the string, the latter element being closer to a true head element of the string.
Since distributed processing systems are often employed to process large amounts of data, such as in the case of image processing, it is always desirable to provide means for performing processing more quickly and efficiently. With respect to an operation such as string length determination, it is highly desirable to provide a method for performing the length determination as rapidly and as efficiently as possible. Such manipulations when performed on a distributed processing system offer the opportunity to enhance operating speed by performing operations in parallel on all string elements.
It is therefore a principal object of the present invention to provide an efficient method for the determination of data string lengths on a distributed processing system.